PrecSezione 17.2: Codifica di canale SuCapitolo 17: Teoria dell’informazione e codifica Chapter 18: Codifica di sorgente multimedialeSegue

## 17.3Codici di canale↓

Dopo aver esposto i risultati che la teoria dell’informazione fornisce a riguardo delle migliori prestazioni ottenibili, proseguiamo il discorso iniziato al § 5.4.3.1↑ relativo a come aggiungere ridondanza↓ ad un flusso binario a velocità fb da trasmettere su di un canale numerico, in modo da realizzare una protezione fec capace di ridurre la probabilità di errore sul bit Pe in ricezione. Notiamo subito che, mentre la soluzione teorica basata su segnalazione asintoticamente ortogonale di fig. 17.13↑ prevede un aumento esponenziale della banda occupata, le tecniche che verranno illustrate consentono di mantenere la relazione tra grado di protezione e banda occupata di tipo proporzionale.
Riprendiamo la notazione introdotta a pag. 1↑ per i codici a blocchi↓, in cui per ogni k bit in ingresso sono prodotte codeword↓↓ con lunghezza n=k+q>k mediante l’aggiunta di q bit di protezione in funzione dei primi k: indichiamo questo procedimento come un codice (n,k), la cui efficienza è misurata dal tasso di codifica↓ (code rate)
Rc=(k)/(n)< 1
che rappresenta la frazione di bit informativi sul totale di quelli trasmessi. La nuova velocità di trasmissione vale pertanto
f’b=(fb)/(Rc)
La teoria esposta al § 17.2.3↑ afferma che la probabilità di errore può essere resa piccola a piacere purché fb=R<C, ma se questo limite è applicato alla effettiva velocità di segnalazione f’b, allora il massimo tasso di trasferimento dell’informazione si riduce a fb=Rcf’b<RcC. Inoltre, aumentando la velocità di segnalazione (essendo f’b>fb) diminuisce di pari misura il rapporto Eb⁄N0=(Px)/(N0f’b) , e conseguentemente peggiora anche la probabilità di errore del decisore, in modo che la capacità correttiva del codice deve essere tale da compensare anche quest’altro fattore. In definitiva, vorremmo trovare codificatori per cui Rc sia il più possibile vicino ad uno.
Al tempo stesso, la capacità di correzione del codice è direttamente legata alla minima distanza↓ di Hamming dm definita a pag. 1↑ come il minimo numero di bit diversi tra due parole di codice, sussistendo le relazioni

- per accorgersi di l (o meno) errori per codeword occorre dm≥l+ 1
- per correggere t (o meno) errori per codeword occorre dm≥ 2t+ 1

Un codice è tanto più potente quanti più errori è in grado di correggere, e dunque deve possedere dm elevato. In un codice a blocchi (n,k) i k bit del messaggio originale assumono tutte le configurazioni possibili, e quindi contribuiscono alla distanza tra codeword per un solo bit; per ottenere dm> 1 occorre pertanto sfruttare gli n−k=q bit di protezione, portando a scrivere
dm≤n−k+ 1 =q+ 1
che evidenzia la relazione tra d e la quantità di bit aggiunti q. L’uguaglianza sussiste solo per una particolare classe di codici [762] [762]Indicati come codici mds, vedi `http://en.wikipedia.org/wiki/Singleton_bound#MDS_codes`. tra cui il codice a ripetizione, discusso a pag. 1↑, che adottando una dimensione di blocco in ingresso k= 1 ha un tasso di codifica Rc=k⁄n=1⁄n molto inefficiente. Mostriamo allora delle soluzioni che consentono di ottenere un adeguato potere di detezione senza per questo aumentare di molto la velocità di trasmissione del flusso codificato.

### 17.3.1Codice lineare a blocchi↓

Le proprietà di questa classe di codici di canale possono essere meglio analizzate interpretando l’insieme delle possibili codeword da un punto di vista algebrico, che ci porta ad adottare una notazione matriciale idonea a descrivere la classe di codici a blocchi, mentre per i codici ciclici interverrà una notazione polinomiale.
Distanza dm per codici lineari
Scegliamo di rappresentare una codeword arbitraria x di un codice a blocchi (n,k) mediante un vettore ad elementi binari
x=(x1 x2 ⋯ xn)
che può assumere solo 2k diversi valori tra i 2n possibili, mentre le ricezione di una delle rimanenti 2n− 2k combinazioni di bit segnala la presenza di almeno un errore. Le 2k codeword costituiscono uno spazio lineare (pag. 1↑) se comprendono la codeword nulla, e se la somma di due vettori è anch’essa una parola di codice. La somma tra due codeword è definita in base alla matematica binaria modulo due, espressa mediante l’operatore di or esclusivo ⊕ come
x+y=(x1⊕y1 x2⊕y2 ⋯ xn⊕yn)
Indicando ora come peso w(z) di un vettore z il numero di suoi elementi non zero, una conseguenza della linearità è la possibilità di valutare la minima distanza↓ di Hamming dm tra parole di codice come il minimo peso tra tutte le codeword non zero [763] [763]Infatti dalla definizione di somma otteniamo che la distanza tra due codeword x e y è pari al peso della codeword z=x+y: infatti z presenterà componenti zj= 1 solo in corrispondenza di elementi xj≠yj. Ma per la linearità anche z appartiene al codebook, e dunque la ricerca su tutte le coppie si trasforma in una ricerca su tutte le codeword., ossia
dm=minx≠ 0[w(x)]
Rappresentazione matriciale per codici sistematici↓
Finora abbiamo assunto che gli n bit delle codeword rappresentino per primi i k bit da proteggere, a cui seguono i q=n−k bit di protezione, anche se questa ripartizione non è per nulla scontata: qualora effettivamente si verifichi, il codice risultante viene detto sistematico. In tal caso le codeword possono essere scritte nella forma
x=(m1 m2 ⋯ mk c1 c2 ⋯ cq)
ovvero in forma partizionata x=(m|c), che consente di rappresentare x a partire dai bit da proteggere m e dalla definizione di una matrice generatrice↓ k×n con struttura generale G=[Ik|P], in cui Ik è una matrice identità k×k e P è una sotto-matrice di elementi binari k×n, permettendo di scrivere x=m⋅G, ovvero
(18.118) [ m1⋯mk c1⋯cq ]=[ m1⋯mk ]⋅⎡⎢⎢⎢⎣ 1 ⋯ 0 p11 ⋯ p1q ⋮ 1 ⋮ ⋮ ⋱ ⋮ 0 ⋯ 1 pk1 ⋯ pkq ⎤⎥⎥⎥⎦
in modo che P produca [764] [764]Sono valide le normali regole di moltiplicazione tra matrici, tranne per l’accortezza di usare la somma modulo due anziché quella convenzionale. i q bit di protezione come c=m⋅P. Dato che il valore della (generica) j-esima componente di c si calcola come
cj=m1p1j⊕m2p2j⊕⋯⊕mkpkj
osserviamo che ciascuna colonna di P individua un sotto-insieme di componenti di m su cui calcolare una somma di parità↓, ed è per questo che il sotto-blocco di matrice è rappresentato dalla lettera P. Ma non è ancora stato definito nulla che ci possa aiutare a scegliere i coefficienti pij allo scopo di ottenere i valori dm e Rc desiderati: il codice di Hamming ci fornisce una possibile soluzione.

#### 17.3.1.1Codice di Hamming↓

q | n | k | Rc
3 | 7 | 4 | 0.57
4 | 15 | 11 | 0.73
5 | 31 | 26 | 0.84
6 | 63 | 57 | 0.9
7 | 127 | 120 | 0.94

E’ un codice a blocchi (n,k) sistematico con q≥ 3 bit di controllo, e per il quale si definisce
n= 2q− 1 e k=n−q
per cui il tasso di codifica vale
Rc=(k)/(n)=(n−q)/(n)= 1 −(q)/(2q− 1)
che aumenta con il crescere di q, come mostrato in tabella. Le codeword si individuano ponendo le righe della sottomatrice P pari a tutte le parole di q bit con due o più uni, in qualsiasi ordine. Ma la cosa più simpatica, è che per un codebook↓ siffatto si ottiene una distanza di Hamming minima dm= 3, indipendentemente dalla scelta di q.
Esempio: codice di Hamming (7,  4). Consideriamo un codice di Hamming con q= 3, e quindi n= 23− 1 = 7 e k= 7 − 3 = 4. Una possibile matrice generatrice è quindi pari a
G=⎡⎢⎢⎢⎢⎢⎣ 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ||||||| 1 0 1 1 1 1 1 1 0 0 1 1 ⎤⎥⎥⎥⎥⎥⎦
a cui corrispondono le seguenti 24= 16 codeword, confermando che dm= 3.

m | c | w(x)
0 0 0 0 | 0 0 0 | 0
0 0 0 1 | 0 1 1 | 3
0 0 1 0 | 1 1 0 | 3
0 0 1 1 | 1 0 1 | 4
0 1 0 0 | 1 1 1 | 4
0 1 0 1 | 1 0 0 | 3
0 1 1 0 | 0 0 1 | 3
0 1 1 1 | 0 1 0 | 4

m | c | w(x)
1 0 0 0 | 1 0 1 | 3
1 0 0 1 | 1 1 0 | 4
1 0 1 0 | 0 1 1 | 4
1 0 1 1 | 0 0 0 | 3
1 1 0 0 | 0 1 0 | 3
1 1 0 1 | 0 0 1 | 4
1 1 1 0 | 1 0 0 | 4
1 1 1 1 | 1 1 1 | 7

Correzione basata sulla distanza
Indichiamo ora con y la parola di codice ricevuta; in presenza di errori, risulta y≠x. Il metodo diretto per rivelare ed eventualmente correggere gli errori presenti è quello di confrontare gli n bit ricevuti con tutte le possibili 2k codeword, e se nessuna di queste risulta uguale ad y, scegliere la x̂ con la minima distanza di Hamming, ossia quella per la quale il peso w(y⊕x̂) è minimo, ovvero
x̂= argmin x {w(y⊕x)}
Correzione basata sulla sindrome↓
Un metodo che non richiede una ricerca esaustiva si basa invece sul calcolo della cosiddetta sindrome, ottenuta mediante moltiplicazione del vettore y ricevuto per una matrice n×q di controllo parità↓ H, definita come H=⎡⎣(P)/(Iq)⎤⎦ in cui P è la stessa matrice di parità utilizzata nella matrice generatrice G, e Iq è una matrice identità di dimensioni q×q. La matrice H esibisce la simpatica proprietà che, se moltiplicata per una qualunque codeword valida, fornisce un vettore nullo di dimensione q, ossia
x⋅H=(0 0 ⋯ 0)
Al contrario, se moltiplicata per un vettore y non appartenente al codebook, fornisce un vettore detto sindrome s=y⋅H non nullo, e quindi il suo calcolo permette la rivelazione (nei limiti consentiti da dm) dell’occorrenza di errori.
H=⎡⎢⎣ 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 0 0 0 1 ⎤⎥⎦
Esempio considerando di nuovo il caso di q= 3, la corrispondente matrice di controllo parità H=⎡⎣(P)/(Iq)⎤⎦ è mostrata a lato. E’ facile verificare che per tutte le possibili codeword x (ad es. x=[0100111]) si ottiene x⋅H=[000]. Poniamo ora che si verifichi una sequenza di errore e=[0010010], dando luogo alla ricezione della parola y=x⊕e=[0110101]: per essa si ottiene una sindrome s = y⋅H=[100].
Per quanto riguarda la correzione, se scriviamo il vettore ricevuto come y=x⊕e, dove e è un vettore di n bit le cui componenti sono diverse da zero in corrispondenza dei bit errati di y, il calcolo della sindrome risulta
s=y⋅H=(x⊕e)⋅H=x⋅H⊕e⋅H=e⋅H
visto che come detto sopra, la sindrome delle codeword è nulla. Dato però che la sindrome ha dimensione di q elementi, tutte le 2n possibili sequenze di errore e danno luogo a sole 2q diverse sindromi, e quindi la conoscenza della sindrome non consente di risalire direttamente a e. Ma riprendendo i risultati esposti a pag. 1↑, risulta che la probabilità P(i,n) che si siano verificati i errori su n bit decresce al crescere di i, e pertanto il vettore ê che con maggior probabilità ha prodotto ognuna delle 2q sindromi s≠ 0, è quello (tra tutti quelli che producono la stessa s) con il minor peso:
ê=argmin e:e⋅H=s {w(e)}
Anziché effettuare questo calcolo ad ogni codeword ricevuta, si può precalcolare, per ogni possibile e, la relativa sindrome, e compilare una tabella T(s) in cui memorizzare per ogni possibile s, il vettore ê di peso minore che la produce. La stessa tabella può quindi essere consultata usando come chiave di ricerca la sindrome s≠ 0 calcolata per ogni y ricevuto, ottenendo il vettore di errore ê=T(s) più probabile, e che se sommato ad y, permette la correzione degli errori. La figura che segue riepiloga i passi necessari alla correzione mediante sindrome.
Osservazioni
Notiamo che se si verificano più errori di quanti dm permetta di correggere, è inutile (anzi dannoso) cercare di eseguire la correzione, perché il numero di errori complessivo può risultare ancora più elevato. Nel caso del codice di Hamming in cui dm= 3 si può correggere un solo errore per codeword, ed esistono solo n vettori e di peso unitario, a cui corrispondono sindromi esattamente pari alle n= 2q− 1 righe di H. Ma se ad esempio e contiene due errori, la sua moltiplicazione per H produce comunque una delle 2q possibili sindromi, ed il tentativo di correzione produce un vettore x̂ contenente tre errori.
Esempio Un gruppo di bit 1001 è protetto dal codice di Hamming di pag. 1↑ producendo x= 1001110, mentre in ricezione si osserva y= 1101110. Il calcolo della sindrome s=y⋅H fornisce il risultato s= 111, che corrisponde alla seconda riga di H, ovvero al vettore di errore ê=  0100000, cioè proprio quello che si è verificato. Se invece avvengono due errori, e si riceve ad es. y= 1111110, si ottiene s= 101, a cui corrisponde ê= 1000000, e quindi il calcolo x̂=y⊕ê produce ora x̂= 0111110, che appunto contiene tre errori.
Per il motivo illustrato, nel caso in cui gli errori non siano indipendenti e dunque isolati nel tempo, ma avvengano in sequenza come nel caso del fast fading (§ 286↑), il solo codice di Hamming è del tutto inadeguato alla loro correzione, mentre una soluzione comunemente adottata è quella di ricorrerre alla tecnica dell’interleaving↓ (§ 5.4.3.3↑) in cui m codeword di lunghezza n uscenti dal codificatore sono scritte per righe, e quindi lette per colonne prima di trasmettere il flusso numerico risultante: ciò consente di correggere fino ad m errori consecutivi, in quanto in ricezione il processo inverso di de-interleaving ridistribuisce i bit errati su m diverse codeword. In alternativa, si possono utilizzare le soluzioni descritte nel seguito.
Soft decision decoding↓
Finora la decodifica di canale è stata applicata a valle del processo di decisione [765] [765]Per questo detta hard decision decoding in quanto opera su decisioni già prese., in modo da individuare le codeword come quelle con la minima distanza di Hamming rispetto al risultato prodotto dal decisore. Se invece le due operazioni sono fuse in un unico elemento che opera su interi blocchi di n bit y=(y1,y2, ⋯,yn), e che tenta di individuare le codeword trasmesse come quelle con la minima distanza euclidea rispetto a quanto ricevuto [766] [766]Tale possibilità è indicata come soft decision decoding (decodifica con decisioni soffici) in quanto richiede operazioni in virgola mobile; si veda ad es. la spegazione fornita presso `http://www.gaussianwaves.com/2009/12/hard-and-soft-decision-decoding-2/`., si ottengono prestazioni migliori a spese di una maggior complessità di calcolo. Questa seconda tecnica valuta le distanze dE(y,xj)=∑ni= 0(yi−xji)2 tra i valori yi effettivamente ricevuti, e quelli che avrebbero dovuto essere nell’ipotesi che sia stata trasmessa una delle possibili codeword xj=(xj1,xj2, ⋯,xjn), decidendo quindi per la codeword x̂j tale che dE(y,x̂j) è minima [767] [767]Si veda lo sviluppo a pag. 1↑ per mettere in relazione la distanza dE(y,xj) con la verosimiglianza logaritmica ln(pn(y⁄xj)) della v.a. n−dimensionale y rispetto all’ipotesi che sia stata trasmessa la codeword xj, in presenza del rumore gaussiano n in sede di decisione.. In tal modo si ottengono prestazioni equivalenti a quelle dell’approccio hard decoding operante con un Eb⁄N0 di circa 2 dB più elevato.

#### 17.3.1.2Codici ciclici↓

Sono un sottoinsieme dei codici lineari a blocchi, con la condizione aggiuntiva che se x=(x1,x2,  ⋯,xn) è una codeword, lo sono anche tutti i sui scorrimenti ciclici [768] [768]Ad esempio, il codice [000, 110, 101, 011] è un codice ciclico, mentre [000,  010, 101, 111] no. , ovvero le codeword x(1)=(x2,x3, ⋯,x1), x(2)=(x3,x4,  ⋯,x2), ⋯, x(n)=(xn,x1, ⋯,xn− 1). In tal caso sussitono delle proprietà algebriche aggiuntive che si basano sulla teoria dei campi di Galois [769] [769]`http://it.wikipedia.org/wiki/Campo_finito`, i cui elementi sono polinomi x(p)=x1pn− 1+x2pn− 2+ ⋯  +xn− 1p+xn nella variabile p, con coefficienti definiti a partire dagli elementi delle codeword x; per tale motivo, i codici ciclici sono detti anche codici polinominali↓ [770] [770]Si veda `http://en.wikipedia.org/wiki/Polynomial_code`: senza volerci addentrare nei particolari della teoria [771] [771]`http://en.wikipedia.org/wiki/Cyclic_code`, citiamo direttamente i principali risultati.
Un codice ciclico (n,k) è completamente definito a partire da un polinomio generatore↓ g(p)=pn−k+g2pn−k− 1+ ⋯ +gn−kp+ 1 di grado n−k e che deve risultare un divisore di pn+ 1, ovvero essere tale che pn+ 1⁄g(p)=q(p) con resto nullo [772] [772]Si applicano le regole di divisione tra polinomi `http://it.wikipedia.org/wiki/Divisione_dei_polinomi`. Una volta definito g(p), è possibile ottenere la matrice generatrice↓ G del codice in forma sistematica G=[Ik|P], calcolando le k righe di P come i coefficienti del polinomio resto della divisione tra pi e g(p), con i=n− 1,n− 2, ⋯,n−k.
Esempio Troviamo la matrice generatrice in forma sistematica per un codice ciclico (7,  4). Osserviamo innanzitutto che pn+ 1 si fattorizza come pn+ 1 =(p+ 1)(p3+p2+ 1)(p3+p+ 1), e scegliamo g(p)=p3+p2+ 1 come polinomio generatore. Il calcolo di pi⁄p3+p2+ 1 per i=  6, 5, 4, 3 fornisce come resti i polinomi p2+p, p+ 1, p2+p+ 1, p2+ 1, pertanto la matrice generatrice risulta G=⎡⎢⎢⎢⎢⎢⎣ 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ||||||| 1 1 0 0 1 1 1 1 1 1 0 1 ⎤⎥⎥⎥⎥⎥⎦. Osserviamo che, a parte una permutazione, le righe di P sono le stesse di quelle che definiscono il codice di Hamming di pag. 1↑: infatti, anche quest’ultimo rientra nella classe dei codici ciclici.
D’altra parte nel caso di un codice ciclico le codeword x associate ai bit m da proteggere possono ottenersi non solo utilizzando G come descritto dalla (18.118↑), ma anche in base alla seguente proprietà: indicando con m(p)=m1pk− 1+m2pk− 2+ ⋯  +mk− 1p+mk il polinomio associato ai k bit da codificare, il polinomio associato alla corrispondente codeword x si ottiene come il prodotto x(p)=m(p)⋅g(p), e quindi gli elementi xi della codeword sono individuati come la convoluzione discreta [773] [773]Il valore dei coefficienti del polinomio prodotto è indicato anche come prodotto di Cauchy (vedi `http://it.wikipedia.org/wiki/Prodotto_di_Cauchy`), e che si ottenga come una convoluzione è facilmente verificabile: dati ad es. a(p)=a0+a1p+a2p2 e b(p)=b0+b1p, si ottiene c(p)=a0b0+(a0b1+a1b0)p+a2p2=∑2i= 0pi∑2j= 0ajbi−j. La notazione lievemente diversa del testo, è dovuta al diverso modo di indicizzare i coefficienti. tra i coefficienti di m(p) e g(p): xi=∑kj= 1mjgi−j+ 1 per i= 1,  2, ⋯,n, operazione che può essere realizzata mediante un filtro fir con coefficienti dati dai valori gi.
Notiamo infine che nel testo si è già incontrato un codice polinomiale (e quindi ciclico) al § 5.4.2.3↑ a proposito del crc: i q bit di protezione possono quindi essere anche ottenuti mediante l’utilizzo di un registro a scorrimento controreazionato [774] [774]Forse ho trovato dove si spiega come faccia un registro a scorrimento controreazionato a svolgere questo genere di compiti: penso che in una prossima edizione sarà interessante aggiungerlo., e lo stesso può essere usato anche per il calcolo della sindrome dal lato ricevente.
Codice BCH↓
Prende il nome dalle iniziali dei rispettivi inventori, e rappresenta una sottoclasse dei codici ciclici, in grado di correggere fino a t<n errori: per ottenere questo risultato occorre scegliere un numero di bit di protezione q≤mt in cui m≥ 3 è un intero, una lunghezza delle codeword pari a n= 2m− 1, ed un polinomio generatore g(p) di grado massimo mt le cui radici sono potenze dell’elemento primitivo α del campo di Galois GF(2m) [775] [775]`http://en.wikipedia.org/wiki/BCH_code`. In tal caso si ottiene dm≥ 2t+ 1, e la capacità di correggere fino a t errori. Nel caso in cui t= 1, si ricade nel caso dei codici di Hamming. La fase di correzione degli errori può essere realizzata mediante il calcolo di una sindrome, per mezzo di una matrice di controllo H realizzata a partire dalle potenze dell’elemento primitivo α, o sfruttando nuovamente proprietà algebriche, che eventualmente si traducono i soluzioni circuitali basate su registri a scorrimento controreazionati. Inoltre, è anche possibile applicare l’algoritmo iterativo di Berlekamp-Massey [776] [776]`http://en.wikipedia.org/wiki/Berlekamp-Massey_algorithm`.
Codice di Reed-Solomon↓
Si tratta di un sottoinsieme dei codici bch, caratterizzato [777] [777]`http://en.wikipedia.org/wiki/Reed-Solomon_error_correction` da parole di codice ad elementi non binari ma bensì L-ari; scegliendo L= 2k si possono mappare k bit della sequenza informativa m in un singolo elemento del codice. Un codice di Reed Solomon (N,K) pone quindi in corrispondenza K simboli ad L livelli prelevati da m, in N simboli ad L livelli della codeword, che viene poi trasmessa
mediante un sistema di modulazione eventualmente anch’esso ad L livelli. I parametri del codice di Reed-Solomon sono espressi dalle relazioni N=L− 1 = 2k− 1, K= 1, 3, ⋯,N− 2 e dm=N−K+ 1, ed è in grado di correggere fino a t=(dm− 1)/(2) simboli L−ari per codeword; il codice è quindi particolarmente indicato nel caso in cui gli errori siano raggruppati te loro, dato che probabilmente incidono su di un solo simbolo (o due).

### 17.3.2Codice convoluzionale↓

Individua un modo di realizzare la codifica di canale che, a differenza dei codici a blocchi, produce una sequenza binaria i cui valori dipendono da gruppi di bit di ingresso temporalmente sovrapposti, in analogia all’integrale di convoluzione che fornisce valori che dipendono da intervalli dell’ingresso, pesati dai valori della risposta impulsiva. Un generico codice convoluzionale è indicato con la notazione CC(n,k,K), che lo descrive capace di generare gruppi di n bit di uscita (sequenza {b}) in base alla conoscenza di K simboli di ingresso (sequenza {a}), ognuno composto da k bit.
La memoria dei K ingressi è usualmente rappresentata mediante un registro a scorrimento che ospita gli ultimi K⋅k bit di ingresso, dove per ogni nuovo simbolo aj che entra da sinistra, i precedenti scorrono a destra, ed il più “vecchio” viene dimenticato. Ognuno degli n bit di uscita bj(i), i= 1,  2, ...,n è ottenuto a partire dai k⋅K bit di memoria, eseguendo una somma modulo 2 tra alcuni di essi [778] [778]Gli n modi di scegliere quali dei k⋅K bit sommare, per ottenere ognuno degli n bit di uscita, sono determinati mediante n vettori generatori gi, i= 1, 2, ...,n, di lunghezza k⋅K, contenenti una serie di cifre binarie zero od uno, a seconda che l’i-esimo sommatore modulo due sia connesso (o meno) al corrispondente bit di memoria.. Resta valido quindi il concetto di coding rate Rc=(k)/(n) che rappresenta quanti bit di informazione sono presenti per ogni bit di uscita dal codificatore.
Diagramma di transizione↓
Una volta definito il meccanismo di calcolo di bj a partire da aj, il codificatore può essere descritto mediante un diagramma di transizione, costituito da 2(K− 1)k stati S associati a tutte le possibili combinazioni di bit degli ultimi K− 1 simboli di ingresso; ad ogni stato competono quindi 2k transizioni, una per ogni possibile nuovo aj di ingresso, ed ognuna delle quali termina sul nuovo stato che si è determinato. Ad ogni transizione, è infine associato in modo univoco il gruppo di n bit bj(aj,Sj) da produrre in uscita [779] [779]Lo stesso valore di bi potrebbe essere prodotto da più di una delle 2k⋅K diverse memorie del codificatore..
Esempio: CC(2,1,3)
Per fissare le idee, definiamo un CC(n,k,K)=CC(2, 1, 3) con g1=[ 1 1 1 ] e g2=[ 1 0 1 ], caratterizzato da un coding rate (1)/(2), e mostrato nella parte sinistra della figura 17.20↓. Per questo, costruiamo il diagramma di transizione mostrato al centro, in cui le transizioni tra stati sono tratteggiate o piene, in corrispondenza rispettivamente dei valori aj pari a zero o ad uno, e sono etichettate con la coppia di bit in uscita bj, calcolabile mediante i vettori generatori g1,  2, come risulta dalla tabella della verità mostrata a destra.

aj | Sj | bj(1) | bj(2)
0 | 00 | 0 | 0
0 | 01 | 1 | 1
0 | 10 | 1 | 0
0 | 11 | 0 | 1
1 | 00 | 1 | 1
1 | 01 | 0 | 0
1 | 10 | 0 | 1
1 | 11 | 1 | 0

Figure 17.20Architettura del codice convoluzionale CC(2,  1, 3), diagramma di transizione e tabella della verità.
Come si può notare, ogni stato ha solo due transizioni, e quindi solo due valori di uscita (la metà dei 4 possibili con due bit); inoltre, questi valori differiscono in entrambi i bit [780] [780]La dipendenza di bj da (aj,Sj) è legata alla scelta dei generatori gi. Nel caso in cui un valore bj(i) sia sempre uguale ad uno dei k bit di aj, il codice è detto sistematico. La scelta dei gi può essere effettuata mediante simulazioni numeriche, per individuare il gruppo che determina le migliori prestazioni..
Qualora si ponga in ingresso la sequenza {a}={...010100}( [781] [781]Per comodità di rappresentazione, il bit più a destra nella sequenza {a} è il primo in ordine di tempo ad entrare nel codificatore.), è possibile osservare che la sequenza di stati risulta {S}={..., 01, 10, 01, 10, 00}, mentre quella di uscita è {b}={..., 10, 00,  10, 11}, semplicemente seguendo il diagramma di transizione, a partire dallo stato iniziale 00. D’altra parte, è possibile anche il procedimento opposto: conoscendo {b}, si può risalire ad {a}, percorrendo di nuovo le transizioni etichettate con i simboli bj. In definitiva, osserviamo come ad ogni coppia ({a},{b}) sia biunivocamente associata una sequenza di stati {S}.
Diagramma a traliccio↓
Per meglio visualizzare le possibili sequenze di stati, costruiamo il diagramma a traliccio (trellis) del codificatore, mostrato a sinistra di fig. 17.21↓
Figure 17.21Diagramma a traliccio e costi dH per la sequenza ricevuta
riportando sulle colonne i possibili stati attraversati ai diversi istanti j, collegando i nodi del traliccio con transizioni piene o tratteggiate nei casi in cui siano relative ad ingressi pari ad 1 o 0, e riportando sulle transizioni stesse i valori di uscita. Con riferimento alla sequenza codificata {b} riportata in basso, l’effettiva successione di stati {S} è rappresentata dalle linee più spesse.
Decodifica di Viterbi↓↓
Consideriamo ora il caso in cui la sequenza codificata {b} venga trasmessa su di un canale, e che sia ricevuta con errori. In generale, non sarà più possibile rintracciare una sequenza di stati tale da produrre esattamente la sequenza ricevuta {b̃}, ed il problema diviene quello di individuare la sequenza di stati {S} tale da produrre una {b̂} la più vicina a {b̃}. Allo scopo di misurare questa differenza, utilizziamo la distanza di Hamming dH(^b,b̃) pari al numero di bit diversi tra {b̃} e le possibili {b̂}( [782] [782]Questo caso viene indicato con il termine hard-decision decoding in quanto il ricevitore ha già operato una decisione (quantizzazione) rispetto a b̃. Al contrario, se i valori ricevuti sono passati come sono al decodificatore di Viterbi, questo può correttamente valutare le probabilità p(b̃⁄^b) ed operare in modalità soft decoding, conseguendo prestazioni migliori.), e etichettiamo gli archi del traliccio con le dH(^bj,b̃j) tra il simbolo da emettere ^bj e quello osservato in ricezione b̃j (vedi lato destro di fig. 17.21↑). In tal modo, per ogni particolare sequenza di stati {S} è possibile determinare un costo pari alla somma delle dH(^bj,b̃j) relative alle transizioni attraversate dal traliccio [783] [783]Ad esempio, con riferimento alla fig. 17.21↑, la {S}={00, 10,  11, 01, 10} ha un costo pari a 3.. Pertanto, la sequenza {b̂} più vicina a {b̃}, ossia tale che
dH(^b,b̃)= min{S}{ ⎲⎳jdH(bj,b̃j)}
può essere individuata come quella associata alla sequenza di stati {Ŝ} di minimo costo [784] [784]Qualora la distanza tra b̃j ed un possibile ^bj sia espressa come probabilità condizionata p(b̃j⁄^bj), il processo di decodifica è detto di massima verosimiglianza↓..
Dato che da ogni stato si dipartono 2k archi, ad ogni istante il numero di percorsi alternativi aumenta di un fattore 2k, crescendo molto velocemente all’aumentare di j. L’enumerazione completa dei percorsi può essere però evitata, notando che quando due percorsi con costi diversi si incontrano in uno stesso nodo, quello di costo maggiore sicuramente non è la parte iniziale del percorso di minimo costo, e quindi può essere eliminato.
Questa filosofia si applica al caso in questione con riferimento alla figura che segue, che mostra come il calcolo dei costi parziali avvenga per colonne da sinistra a destra, scrivendo sopra ad ogni nodo il costo del miglior percorso che lo raggiunge. Ad ogni colonna sono scartati i percorsi che si incontrano con uno migliore, cosicchè il numero di percorsi sopravvissuti è sempre pari al numero di stati 2k.
All’estremità destra della figura una freccia indica la minima dH(^b,b̃), associata al percorso a tratto spesso, e che permette di individuare la {b̃}, che come si vede è quella esatta.
Tralasciamo ora di approfondire la teoria che consente l’analisi dettagliata dell’algoritmo, e ci limitiamo alle seguenti
Riflessioni

- l’esempio fornito si mostra in grado di correggere un errore pur impiegando un coding rate pari ad (1)/(2), migliore (ad es.) di quello ⎛⎝(1)/(3)⎞⎠ del codice a ripetizione;
- la dH del miglior percorso corrisponde al numero di bit errati (nel caso in cui siano stati corretti) nella b̃ ricevuta;
- si verifica errore (cioè {b̂} ≠{b}) se dH(^b,b̃) è minore di dH(b,b̃);
- le capacità di correzione del codice migliorano aumentando la dH tra le possibili sequenze {b} [785] [785]La minima distanza tra le sequenze codificate è indicata come dmin, e può essere trovata come la dH tra una {b0} tutta nulla ({b0}={...000000000}) e quella con il minor numero di uni, che si diparte e ritorna (nel traliccio) dallo/allo stato 00.;
- la dH tra diverse {b} aumenta con (K)/(k), in quanto la matrice di transizione tra stati diviene più sparsa, ed i valori di {b} sono più interdipendenti;
- se il miglioramento di cui sopra è ottenuto aumentando K, ciò equivale ad estendere nel tempo la memoria del codificatore, ma senza per questo alterare il tasso di codifica Rc=(k)/(n).

PrecSezione 17.2: Codifica di canale SuCapitolo 17: Teoria dell’informazione e codifica Chapter 18: Codifica di sorgente multimedialeSegue